package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 最大子数组和
    static class Solution {
        public int maxSubArray(int[] nums) {
            // 1) 初始化 DP 数组：dp[i] 表示以 nums[i-1] 结尾的最大子数组和
            int m = nums.length;
            int[] dp = new int[m + 1];
            dp[0] = Integer.MIN_VALUE / 2; // 哨兵，避免加法溢出

            // 2) 动态规划：决定是接续前面还是重新开始
            for (int i = 1; i <= m; i++) {
                // 要么延续 dp[i-1]，要么从 nums[i-1] 重新开始
                dp[i] = Math.max(dp[i-1] + nums[i-1], nums[i-1]);
            }

            // 3) 遍历所有位置，找出最大值
            int maxSum = Integer.MIN_VALUE / 2;
            for (int i = 1; i <= m; i++) {
                maxSum = Math.max(maxSum, dp[i]);
            }
            return maxSum;
        }
    }
}